import java.util.*;
public class chap03 {
    public static void main(String[] args) {
        System.out.println("请输入你要进行排序的数字个数：");
        Scanner input1 = new Scanner(System.in);
        // 输入进行排序的数字个数，控制在100以内
        int num = input1.nextInt();
        int[] a = new int[num];
        int k = 0;
        while (k <= num - 1) {
            int t = (int) (Math.random() * 1000);
            // 随机产生0-1000范围内的数字，并确保不重复
            boolean b = false;
            for (int i = 0; i < a.length; i++) {
                if (t == a[i]) {
                    b = true;
                }
            }
            if (b != true) {
                a[k] = t;
                k++;
            }
        }
        input1.close();
        int[] templist = new int[a.length];
        System.arraycopy(a, 0, templist, 0, a.length);
        System.out.println("初始状态： " + Arrays.toString(a) + " 下面进行直接插入排序");
        int[] b = InserSort(a);
        System.out.println("经过直接插入排序后最终状态： " + Arrays.toString(b));
        System.arraycopy(templist, 0, a, 0, templist.length);
        System.out.println("\n\n初始状态： " + Arrays.toString(a) + " 下面进行冒泡排序");
        int[] c = BubbleSort(a);
        System.out.println("经过冒泡排序后最终状态： " + Arrays.toString(c));
        System.arraycopy(templist, 0, a, 0, templist.length);
        System.out.println("\n\n初始状态： " + Arrays.toString(a) + " 下面进行快速排序");
        int[] d = QuickSort(a);
        System.out.println("经过快速排序后最终状态： " + Arrays.toString(d));
    }
    public static int[] InserSort(int[] a) { // 直接插入算法 insertion sort
        int i, j, num = 0;
        // 角标从第二个值开始，遍历所有值
        for (i = 1; i < a.length; i++) {
            // 每次排序a[i]与前面的所有值比较
            for (j = 0; j <= i; j++) {
                // 如果大，则前面的数据不动
                if (a[i] < a[j]) {
                    // 如果小，则插入到数列中，所有数据往后移动
                    int temp = a[i];
                    for (int k = i; k > j; k--) {
                        a[k] = a[k - 1];
                    }
                    a[j] = temp;
                }
            }
            System.out.println("第 " + (++num) + " 趟排序： " + Arrays.toString(a));
        }
        return a;
    }
    public static int[] BubbleSort(int[] a) { // 冒泡算法 bubble sort
        int n = a.length; // 数组长度
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    // 交换 a[j] 和 a[j+1]
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
            System.out.println("第 " + (i + 1) + " 趟排序： " + Arrays.toString(a));
        }
        return a;
    }
    public static int[] QuickSort(int[] a) { // 快速排序算法 Quick Sort
        quickSort(a, 0, a.length - 1); // 调用快速排序的递归函数
        return a;
    }
    private static void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int pi = partition(a, low, high); // 获取分区点
            quickSort(a, low, pi - 1); // 对左子数组进行递归排序
            quickSort(a, pi + 1, high); // 对右子数组进行递归排序
        }
    }
    private static int partition(int[] a, int low, int high) {
        int pivot = a[high]; // 选择最后一个元素作为基准
        int i = (low - 1); // 较小元素的索引
        for (int j = low; j < high; j++) {
            if (a[j] < pivot) { // 如果当前元素小于基准
                i++;
                int temp = a[i]; // 交换 a[i] 和 a[j]
                a[i] = a[j];
                a[j] = temp;
            }
        }
        int temp = a[i + 1]; // 将基准元素放到正确的位置
        a[i + 1] = a[high];
        a[high] = temp;
        return i + 1; // 返回分区点的索引
    }
}